package main

// https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func flatten(root *TreeNode) {
	for root != nil {
		// 没有左子树，直接考虑下一个节点
		if root.Left == nil {
			root = root.Right
		} else {
			// 找左子树最右边的节点
			pre := root.Left
			for pre.Right != nil {
				pre = pre.Right
			}
			//将原来的右子树接到左子树的最右边节点
			pre.Right = root.Right
			// 将左子树插入到右子树的地方
			root.Right = root.Left
			root.Left = nil
			// 考虑下一个节点
			root = root.Right
		}
	}
}

func LRD(root *TreeNode) {
	if root == nil {
		return
	}
	LRD(root.Left)
	LRD(root.Right)
	if root.Left != nil {
		temp := root.Right
		root.Right = root.Left
		root.Right.Right = temp
		root.Left = nil
	}
}

func main() {

}
